package 分类.二叉树;

import java.util.HashMap;

public class 从前序与中序遍历序列构造二叉树 {
    HashMap<Integer, Integer> hashMap=new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
       for (int i=0;i<inorder.length;i++){
           hashMap.put(inorder[i],i);
       }
       return build(preorder,0,preorder.length-1,inorder,0,inorder.length-1);

    }
    TreeNode build(int[] pre,int prestart,int preend,int[] in,int instart,int inend){
        if(prestart>preend){
            return null;
        }
        int rootval=pre[prestart];
        int index=hashMap.get(rootval);
        int leftsize=index-instart;

        TreeNode root=new TreeNode(rootval);
        root.left=build(pre,prestart+1,prestart+leftsize,in,instart,index-1);
        root.right=build(pre,prestart+leftsize+1,preend,in,index+1,inend);
        return root;
    }

    public static void main(String[] args) {

    }


}
